package ch3.stack.link;//package Link;

class LinkNode<E> {    //链队结点泛型类
    E data;
    LinkNode<E> next;

    public LinkNode() {    //构造方法
        next = null;
    }

    public LinkNode(E d) {    //重载构造方法
        this.data = d;
        this.next = null;
    }
}

public class LinkStackClass<E> {    //链栈泛型类
    LinkNode<E> head;               //存放头结点

    public LinkStackClass() {        //构造方法
        head = new LinkNode<E>();   //创建头结点
        head.next = null;           //设置为空栈
    }

    //栈的基本运算算法
    public boolean empty() {    //判断栈是否为空
        return head.next == null;
    }

    public void push(E e) {    //元素e进栈
        LinkNode<E> s = new LinkNode<E>(e); //新建结点s
        s.next = head.next;                 //将结点s插入到表头
        head.next = s;
    }

    public E pop() {    //出栈操作
        if (empty()) {
            throw new IllegalArgumentException("栈空");
        }
        E e = (E) head.next.data;       //取首结点值
        head.next = head.next.next;     //删除原首结点
        return e;
    }

    public E peek() {    //取栈顶元素操作
        if (empty()) {
            throw new IllegalArgumentException("栈空");
        }
        return (E) head.next.data;   //取首结点值
    }

    @Override
    public String toString() {
        String ans = "";
        if (!empty()) {
            LinkNode<E> p = head.next;
            while (p != null) {
                ans += p.data + " ";
                p = p.next;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        //测试1
        System.out.println("*******测试1****************");
        Integer[] a = {1, 2, 3, 4, 5};
        LinkStackClass<Integer> st1 = new LinkStackClass<Integer>();
        for (int i = 0; i < a.length; i++) {
            st1.push(a[i]);
            System.out.println("进栈元素: " + a[i]);
        }
        System.out.println("st1为空: " + st1.empty());
        System.out.println("st1: " + st1.toString());
        Integer e;
        while (!st1.empty()) {
            e = st1.pop();
            System.out.println("出栈元素: " + e);
        }
        System.out.println("st1为空: " + st1.empty());

        //测试2
        System.out.println("*******测试2****************");
        String[] b = {"a", "b", "c", "d"};
        LinkStackClass<String> st2 = new LinkStackClass<String>();
        for (int i = 0; i < b.length; i++) {
            st2.push(b[i]);
            System.out.println("进栈元素: " + b[i]);
        }
        System.out.println("st2为空: " + st2.empty());
        System.out.println("st2: " + st2.toString());
        String x;
        while (!st2.empty()) {
            x = st2.pop();
            System.out.println("出栈元素: " + x);
        }
        System.out.println("st2为空: " + st2.empty());
    }
}
